#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <stdlib.h>
#include <string>
using namespace std;

//模拟实现vector
template <class T>
class MyVector
{
  public:
    typedef T* Iterator;//用原生指针 类型重定义为 Iterator迭代器 
    typedef const T* const_Iterator;
    MyVector():_start(NULL),_finish(NULL),_end_of_storage(NULL)
    {}
    ~MyVector()
    {
      delete []_start;
      _start=_finish=_end_of_storage=NULL;
    }

    void  PushBack(const T & val)
    {
      //容量不够时就需要扩容
      if(_finish>=_end_of_storage)
      {
        Expand(Capacity()*2+1);
      }
      *_finish=val;
      _finish++;
    }
    void PopBack()
    {
      if(Size()==0)//表示顺序表为空
      {
        return;
      }
      else
      {
        _finish--;
      }
    }
    //*****************对顺序表进行扩容并初始化************************
    void Resize(size_t n ,const T & val=T())
    {
      if(n>Size())
      {
          if(n>Capacity())
          {
            //需要进行扩容
            Expand(n);
          }
          //上面进行扩容后。只是改变了容量
          //并没有改变size
          //然后对size和n之间的元素进行初始化
          //所以要手动的将_finish修改到正确的位置，这样才能保证下面的赋值操作正常进行，否则会段错误的
          _finish=_start+n;
          size_t i=0;
          for(i=Size();i<n;++i)
          {
            _start[i]=val;
          }
      }
      else
      {
        //如果n小于size
        _finish=_start+n;
        //将size减小
      }
    }


    //*****************对顺序表进行赋值************************
    void Assign(size_t n,const T &val= T())
    {
      if(n>Size())
      {
        if(n>Capacity())
        {
          Expand(n);
        }
        _finish=_start+n;
      }
      size_t i=0;
      for(i=0;i<n;++i)
      {
        _start[i]=val;
      }
    }

    //*****************对顺序表进行扩容************************
    void Reserve(size_t n)
    {
      if(n<=Capacity())
      {
        return;
      }
      else
      {
        Expand(n);
      }
    }

    //********************对顺序表进行插入***********************
    Iterator Insert(const Iterator & pos,const T & val)
    {
      assert(pos<=end());//可以进行尾插
      
      if(_finish==_end_of_storage)
      {
        Expand(Capacity()*2+1);
      }
      _finish++;
      size_t i=0;
      for(i=Size();i>pos-begin();--i)
      {
        _start[i]=_start[i-1];
      }
      *pos=val;
    }
    //**********************对顺序表进行删除***********************
    
    Iterator Erase(const Iterator& pos)
    {
      assert(pos<end());

      Iterator cur=pos;
      while(cur<end()-1)
      {
        *cur=*(cur+1);
        cur++;
      }
      _finish--;
    }


    T& operator[](size_t pos)
    {
      assert(pos<Size());
      return _start[pos];
    }
    const T& operator[](size_t pos)const
    {
      assert(pos<Size());
      return _start[pos];
    }
    //****迭代器的接口
    Iterator begin()
    {
      return _start;
    }

    Iterator end()
    {
      return _finish;
    }
    const_Iterator begin() const
    {
      return _start;
    }

    const_Iterator end()  const
    {
      return _finish;
    }
    size_t Size()
    {
      return _finish-_start;
    }
    size_t Capacity()
    {
      return _end_of_storage-_start;
    }

  protected:
    Iterator _start;
    Iterator _finish;
    Iterator _end_of_storage;


    void Expand(size_t n)
    {
      if(n<=Capacity())
      {
        return;
      }
      else
      {
        size_t Size=this->Size();
        //注意这里要将Size()先保存下。
        //因为下面在新开的空间后再进行赋值时用到
        T * new_start=new T[n];
        size_t  i=0;
        //对新开的空间进行赋值。
        //这里不用memcpy()是因为T 的如果是自定义类型的话，存在深浅拷贝的问题
        for(i=0;i<Size;i++)
        {
          new_start[i]=_start[i];
        }
        //释放旧的空间
        delete [] _start;
        _start=NULL;

        //修改新空间的三个指针
        _start=new_start;
        _finish=_start+Size;//这里就不可以用Size()函数来求取Size 因为start位置已经变了
        _end_of_storage=_start+n;
      }
    }
};

